Skip to main content

Top-down synthesis of simple divide and conquer algorithms

Item Preview

texts
Top-down synthesis of simple divide and conquer algorithms


Published November 1982
SHOW MORE


"NPS-52-82-011."

"November 1982."

Cover title

Includes bibliographic references (p. 98-99)

"Prepared for: Chief of Naval Research; Arlington, VA 22217."

Technical report; 1982

A new method is presented for the deductive synthesis of computer programs. The method takes as given a formal specification of a user's problem. The specification is allowed to be incomplete in that some or all of the input conditions may be omitted. A completed specification plus a computer program are produced by the method. Synthesis involves the top-down decomposition of the user's problem into a hierarchy of subproblems. Solving each of these subproblems results in the synthesis of a hierarchically structured program. The program is guaranteed to satisfy the completed specification and to terminate on all legal inputs. In this paper we present a framework for a top-down synthesis process, explore the structure of a class of divide and conquer algorithms, and present a method for the top-down synthesis of algorithms in this class. Detailed derivations of four sorting algorithms are presented. (Author)


Publisher Monterey, California : Naval Postgraduate School
Pages 108
Language en_US
Call number ocm81456374
Digitizing sponsor Naval Postgraduate School, Dudley Knox Library
Book contributor Naval Postgraduate School, Dudley Knox Library
Collection navalpostgraduateschoollibrary; fedlink; americana
Notes some content may be lost due to the binding of the book.

Full catalog record MARCXML

[Open Library icon]This book has an editable web page on Open Library.

comment
Reviews

There are no reviews yet. Be the first one to write a review.
SIMILAR ITEMS (based on metadata)
eye
Title
Date Archived
Creator
Department of Defense
texts
eye 18
favorite 0
comment 0
Department of Defense
by Smith, Douglas R.
texts
eye 22
favorite 0
comment 0
Naval Postgraduate School, Dudley Knox Library
by Smith, Douglas R.
texts
eye 236
favorite 0
comment 0
Naval Postgraduate School, Dudley Knox Library
by Gragg, William B.;Reichel, Lother.
texts
eye 224
favorite 0
comment 0
Naval Postgraduate School, Dudley Knox Library
texts
eye 357
favorite 0
comment 0
Department of Defense
by Smith, Douglas R.
texts
eye 10
favorite 0
comment 0
Naval Postgraduate School, Dudley Knox Library
by Bradley, Gordon H.Brown, Gerald G.Graves, Glenn W.
texts
eye 181
favorite 0
comment 0
Source: half
Naval Postgraduate School, Dudley Knox Library
by Yasutome, Kenneth Kiyoshi
texts
eye 84
favorite 0
comment 0
Source: half